package com.kevinkk.dp;

/**
 * 斐波那契数
 * DP 公式：F(n) = F(n - 1) + F(n - 2)，其中 n > 1
 */

public class FibonacciNumber {
    class Solution {
        public int fib(int n) {
            if (n < 2) return n;
            int a = 0, b = 1, c = 0;
            for (int i = 1; i < n; i++) {
                c = a + b;
                // 先更新 a，然后再更新 b
                a = b;
                b = c;
            }
            return c;
        }
    }
}
